package com.s6.sort3;

import java.util.Arrays;

import com.s6.sort1.ArrayUtils;
import com.s6.sort2.QuickSort;

/**
 * 桶排序算法
 */
public class BucketSort {

	public static void main(String[] args) {
		int[] array = ArrayUtils.randomInt();
		System.out.println("before array = " + Arrays.toString(array));
		bucketSort(array);
		System.out.println("after array = " + Arrays.toString(array));
	}

	public static void bucketSort(int[] arr) {
		if (arr.length < 2) {
			return;
		}
		
		// 在额外空间充足的情况下，尽量增大桶的数量，排序越快。这里桶的数量取得是 数量的开方 + 1
		int bucketCount = (int) (Math.sqrt(arr.length)) + 1;
		System.out.println("bucketCount = " + bucketCount);
		int min, max;
		min = max = arr[0];
		int i, j, k;
		for (i = 1; i < arr.length; i++) {
			if (arr[i] < min) {
				min = arr[i];
			}
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		// 元素映射通下标用到的 key
		int key = (max - min) / bucketCount + 1;
		// 每个桶预设容量
		int bucketSize = key / 2 + 1;
		System.out.println("bucketSize = " + bucketSize);
		int[][] buckets = new int[bucketCount][bucketSize];
		int[] indexArray = new int[bucketCount];

		// 计算该值归为第几个桶
		for (i = 0; i < arr.length; i++) {
			// 元素映射到第 result 个桶
			int bucketIndex = (arr[i] - min) / key;
			int index = indexArray[bucketIndex];
			if (index == buckets[bucketIndex].length) {
				// 扩容
				expand(buckets, bucketIndex);
			}
			buckets[bucketIndex][index] = arr[i];
			indexArray[bucketIndex] = index + 1;
		}

        // 对每个桶进行排序，这里使用了快速排序；并输出全部 buckets 到 arr
		for (i = 0, k = 0; i < bucketCount; i++) {
			QuickSort.sort(buckets[i], 0, indexArray[i] - 1);
			for (j = 0; j < indexArray[i]; j++) {
				arr[k++] = buckets[i][j];
			}
		}
	}

	private static void expand(int[][] buckets, int bucketIndex) {
		int[] arr = buckets[bucketIndex];
		int[] newArr = new int[arr.length * 2];
		for (int i = 0; i < arr.length; i++) {
			newArr[i] = arr[i];
		}
		buckets[bucketIndex] = newArr;
	}

}
